package org.lql.algo.codecrush.hot100.binarySearch;

/**
 * @author: liangqinglong
 * @date: 2025-09-03 22:30
 * @description: 33. 搜索旋转排序数组 <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class Search {

	public int search(int[] nums, int target) {
		int left = 0;
		int right = nums.length - 1;
		while (left < right) {
			int mid = (left + right) >> 1;
			if (nums[mid] <= right) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		int k = right;
		if (nums[k] <= target && target <= nums[nums.length - 1]) {
			return bs(k, nums.length - 1, nums, target);
		} else {
			return bs(0, k - 1, nums, target);
		}
	}

	public int bs(int left, int right, int[] nums, int target) {
		while (left <= right) {
			int mid = (left + right) / 2;
			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		Search search = new Search();
		int[] nums = {4, 5, 6, 7, 0, 1, 2};
		int target = 0;
		// 4
		System.out.println(search.search(nums, target));
		// 0
		System.out.println(search.search(new int[]{1}, 1));
		// -1
		System.out.println(search.search(new int[]{1}, 0));
		// -1
		System.out.println(search.search(new int[]{1, 3}, 2));
		// 0
		System.out.println(search.search(new int[]{3, 1}, 3));
	}
}
